package _4_algorithms;

import java.util.Stack;

public class ZhiFangTu {

  public static void main(String[] args) {
    int[] a = {2, 1, 2, 1, 2};
    int area = largestRectangleArea(a);
    System.out.println(area);
  }

  /**
   * 算法有误,
   *
   * @param height
   * @return
   */
  private static int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
      return 0;
    }
    //stack存储height数组的下标
    Stack<Integer> stack = new Stack<>();
    //最大面积, 当前矩形的高度, 当前矩形的宽度
    int max = 0, ceiling = 0, width = 0;
    /* 依次遍历，若 height[i] < height[stack.peek()] 那么把大于 height[i] 的元素的下标, 出栈，并求取这些元素组成的最大矩形面积
      使得栈中数据始终为递增的，直观上相当于将高的矩块削平了。*/
    for (int i = 0; i <= height.length; i++) {
      while (!stack.isEmpty() && (i == height.length || height[stack.peek()] >= height[i])) {
        int index = stack.pop();
        ceiling = height[index];
        //当前矩行的宽度取决于此时栈顶的下标和此时遍历到的位置i
        if (stack.isEmpty()) {
          width = i;
        } else {
          width = i - stack.peek() - 1;
        }
        max = Math.max(max, ceiling * width);
      }
      if (i < height.length) {
        stack.push(i);
      }
    }
    return max;
  }

}
